<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
            abcde  ace 
            确定dp数组和下标含义：
            很明显，两个序列求公共部分需要用到二维数组
            dp[i][j]表示长度为i的text1和长度为j的text2的最长公共子序列长度为dp[i][j]，注意必须是以(0,text1[i-1])
            
            状态转移方程
            




            */
            var longestCommonSubsequence = function (text1, text2) {
                let dp = new Array(text1.length + 1).fill().map(() => new Array(text2.length + 1).fill(0))
                for (let i = 1; i <= text1.length; i++) {
                    for (let j = 1; j <= text2.length; j++) {
                        if (text1[i - 1] == text2[j - 1]) {
                            dp[i][j] = dp[i - 1][j - 1] + 1
                        } else {
                            dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
                        }
                    }
                }
                return dp[text1.length][text2.length]
            }
        </script>
    </body>
</html>
